The present invention relates to a method and its corresponding device for stimating motion between an incoming frame F(n) of a sequence of frames and a large static image M(nxe2x88x921), said large static image being constructed from previous frames F(1) . . . F(nxe2x88x921) of said sequence, said motion estimation method using a motion model based on a two-dimensional perspective transform containing eight motion parameters and comprising an optimization step of a cost function.
Such an invention can be useful for applications related to MPEG-4 and, more especially, to MPEG-7 standard, such as sprite generation or mosaicing.
A method of the above kind is known from the patent application WO 98/59497. This patent application describes a method used in video coding for generating a sprite from the video objects in the frame of a video sequence. The method estimates the global motion between a video object in a current frame and a sprite constructed from video objects for previous frames. Specifically, the global motion estimation method computes motion coefficients of a two-dimensional transform that minimizes the intensity errors between pixels in the video object and corresponding pixels in the sprite. The Levenberg-Marquardt method is employed for the minimizing step, which consists in the minimization of an analytical function related to the intensity errors, and allows to select the most representative points and reject the others as outliers.
Nevertheless, the previously described global motion estimation method has several drawbacks. The major one is that it is very sensitive to outliers, which are pixels that do not follow the global motion and corresponds to objects having their own motion. It means that the global motion estimation method can sometimes fail with some particular video sequences. Another drawback is also its inability to converge efficiently and fast for certain kind of video sequences.
It is therefore an object of the present invention to propose another global motion estimation method that is very robust to outliers but that can also allow an efficient and fast convergence.
To this end, the method according to the invention is characterized in that the eight motion parameters are the coordinates of the four vertices of the incoming frame, said vertices being successively moved in two directions to find an estimation of the motion parameters corresponding to an optimum of the cost function.
The motion estimation method is based on a geometrical approach that treats successively and iteratively the eight motion parameters by optimizing a numerical function whereas the approach of the background art, based on the Levenberg-Marquardt algorithm, treats the eight motion parameters simultaneously by minimizing an analytical function. As a consequence, the motion estimation method based on the displacement of the four vertices has proved to be more robust to outliers than the one used in the background art.
The method according to the invention is also characterized in that the motion estimation method includes a first iterative method that comprises, at each iteration, the optimization step to determine an estimation of the eight motion parameters, followed by a step of calculation of the two directions of motion of each of the four vertices by taking into account the last deformation, said iterative method being performed until a defined criteria is reached.
The iterative method is based on the Powell""s algorithm that improves the convergence of said method.
The method according to the invention is finally characterized in that the optimization step comprises a second iterative method performing, at each iteration, a parabolic interpolation operation of values of the cost function to estimate successively the motion parameters.
The use of a parabolic interpolation operation makes the convergence of the motion estimation method faster, especially in the case of large motion.
As a consequence, the present motion estimation method could be advantageously included in a method for generating a large static image, such as a sprite or a mosaic, and implemented in a device for generating such a large static image.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.